package algorithm.leetcode.simple;

/*
 给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
 */

/**
 * @author jack.wu
 * @version 1.0
 * @date 2021/1/20
 */
public class Question628 {

    public static void main(String[] args) {
        Question628 question = new Question628();
        int[] nums = {1, 2, 3, 4};
        int maximumProduct = question.maximumProduct(nums);
        System.out.println(maximumProduct);
    }

    /**
     * 思路：
     * 方法一：线性扫描
     * 1、如果数组中全是非负数，则排序后最大的三个数相乘即为最大乘积；
     * 2、如果全是非正数，则最大的三个数相乘同样也为最大乘积。
     * 3、如果数组中有正数有负数，则最大乘积既可能是三个最大正数的乘积，
     * 也可能是两个最小负数（即绝对值最大）与最大正数的乘积。
     *
     * 方法二：排序
     */
    public int maximumProduct(int[] nums) {
        if (nums == null || nums.length < 3) {
            return 0;
        }
        // 第3种情况
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;
        // 1、2种情况
        int max1 = Integer.MIN_VALUE;
        int max2 = Integer.MIN_VALUE;
        int max3 = Integer.MIN_VALUE;

        for (int n : nums) {
            if (n < min1) {
                min2 = min1;
                min1 = n;
            } else if (n < min2) {
                min2 = n;
            }

            if (n > max1) {
                max3 = max2;
                max2 = max1;
                max1 = n;
            } else if (n > max2) {
                max3 = max2;
                max2 = n;
            } else if (n > max3) {
                max3 = n;
            }
        }
        return Math.max((min1 * min2 * max1), (max1 * max2 * max3));

    }

}
